package com.leetcodehot.problems;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class problems2080 {
    /**
     * Your RangeFreqQuery object will be instantiated and called as such:
     * RangeFreqQuery obj = new RangeFreqQuery(arr);
     * int param_1 = obj.query(left,right,value);
     */
    class RangeFreqQuery {
        int length;
        int maxValue;
        int minValue;
        HashMap<Integer, List<Integer>> valueToIndexMap;

        public RangeFreqQuery(int[] arr) {
            length = arr.length;
            valueToIndexMap = new HashMap<>();
            for (int i = 0; i < length; i++) {
                int arrValue = arr[i];
                maxValue = Math.max(maxValue, arrValue);
                minValue = Math.min(minValue, arrValue);
                if (valueToIndexMap.containsKey(arrValue)) {
                    valueToIndexMap.get(arrValue).add(i);
                } else {
                    List<Integer> integers = new ArrayList<>();
                    integers.add(i);
                    valueToIndexMap.put(arrValue, integers);
                }
            }
        }

        public int query(int left, int right, int value) {
            // 得有个valueToIndexMap
            if (!valueToIndexMap.containsKey(value)) {
                return 0;
            }
            if (value < minValue || value > maxValue) {
                return 0;
            }
            List<Integer> integers = valueToIndexMap.get(value);
            int l = -1;
            int r = integers.size();
            while (l + 1 < r) {
                int mid = (l + r) / 2;
                if (integers.get(mid) < left) {
                    l = mid;
                } else {
                    r = mid;
                }
            } // r是第一个位置
            if (r == integers.size()) {
                return 0;
            }
            int ans1 = r;
            l = -1;
            r = integers.size();
            while (l + 1 < r) {
                int mid = (l + r) / 2;
                if (integers.get(mid) <= right) {
                    l = mid;
                } else {
                    r = mid;
                }
            } // l是第二个位置
            return r - ans1;
        }
    }
}
